package com.atwy.graph;

import com.atwy.graph.directedgraph.DepthFirstOrder;
import com.atwy.graph.directedgraph.IDigraph;
import com.atwy.graph.directedgraph.TableDigraph;
import com.atwy.graph.undirectedgraph.BreadthFirstSearch;
import com.atwy.graph.undirectedgraph.DepthFirstSearch;
import com.atwy.graph.undirectedgraph.MatrixGraph;
import com.atwy.graph.undirectedgraph.TableGraph;

import java.util.Arrays;
import java.util.Iterator;

/**
 * 图的案例
 */
public class GraphDemo {
    public static void main(String[] args) {
        //testMatrixGraph();
        System.out.println();
        //testTableGraph();
        System.out.println();

        testDfsOrder();
    }

    /**
     * 6
     * 8
     * 0 5
     * 2 4
     * 2 3
     * 1 2
     * 0 1
     * 3 4
     * 3 5
     * 0 2
     * <p>
     * 6各顶点，8条边
     * 0 5 表示 顶点下标0与5之间有边
     * 答案：
     * V:0,adj->[2][1][5]
     * V:1,adj->[0][2]
     * V:2,adj->[0][1][3][4]
     * V:3,adj->[5][4][2]
     * V:4,adj->[3][2]
     * V:5,adj->[3][0]
     */
    public static void testTableGraph() {

        TableGraph graph = new TableGraph(6);
        graph.addEdge(0, 5);
        graph.addEdge(2, 4);
        graph.addEdge(2, 3);
        graph.addEdge(1, 2);
        graph.addEdge(0, 1);
        graph.addEdge(3, 4);
        graph.addEdge(3, 5);
        graph.addEdge(0, 2);
        graph.print();
        int[] adj = graph.adj(0);
        System.out.println("邻接表的顶点：" + 0 + "邻接顶点集合是：" + Arrays.toString(adj));
        System.out.println("邻接表的dfs--start");
        // 起点为2
        DepthFirstSearch dfs = new DepthFirstSearch(graph, 2);
        // 2到5的路径
        dfs.printPath(5);
        System.out.println("\n邻接表的dfs--end");
        System.out.println();
        System.out.println("邻接表的bfs--start");
        BreadthFirstSearch bfs = new BreadthFirstSearch(graph,2);
        bfs.printPath(5);
        System.out.println("\n邻接表的bfs--end");
    }

    /**
     * 答案：
     * [0, 1, 1, 0, 0]
     * [1, 0, 1, 1, 1]
     * [1, 1, 0, 0, 0]
     * [0, 1, 0, 0, 0]
     * [0, 1, 0, 0, 0]
     */
    public static void testMatrixGraph() {
        MatrixGraph graph = new MatrixGraph(5);
        String[] vertexs = {"A", "B", "C", "D", "E"};
        // 添加顶点
        for (String vertex : vertexs) {
            graph.addVertex(vertex);
        }
        // 添加边
        // A-B,A-C,B-C,B-D,B-E   A的下标是0，B的下标是1
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);

        // 打印图
        graph.showGraph();
        // 和A相邻的顶点
        int[] adj = graph.adj(0);
        System.out.println("邻接矩阵与0顶点相邻的顶点："+Arrays.toString(adj));
        System.out.println("邻接矩阵的dfs--start");
        // 将A点设为起点
        DepthFirstSearch dfs = new DepthFirstSearch(graph, 0);
        int[] edgeTo = dfs.getEdgeTo();
        // 打印A-E的路径
        dfs.printPath(4);
        System.out.println("\n邻接矩阵的dfs--start");

        System.out.println("邻接矩阵的bfs--start");
        BreadthFirstSearch bfs = new BreadthFirstSearch(graph,0);
        bfs.printPath(4);
        System.out.println("\n邻接矩阵的bfs--end");

    }

    /**
     * 测试深度优先的顶点排序
     */
    public static void testDfsOrder(){
        IDigraph graph = new TableDigraph(13);
        graph.addEdge(0,1);
        graph.addEdge(0,5);
        graph.addEdge(0,6);
        graph.addEdge(2,0);
        graph.addEdge(2,3);
        graph.addEdge(3,5);
        graph.addEdge(5,4);
        graph.addEdge(6,4);
        graph.addEdge(6,9);
        graph.addEdge(7,6);
        graph.addEdge(8,7);
        graph.addEdge(9,10);
        graph.addEdge(9,11);
        graph.addEdge(9,12);
        graph.addEdge(11,12);

        DepthFirstOrder dfsOrder = new DepthFirstOrder(graph);
        Iterable<Integer> pre = dfsOrder.pre();
        Iterator<Integer> iterator = pre.iterator();
        System.out.println("pre:");
        while (iterator.hasNext()){
            System.out.print(iterator.next()+"\t");
        }
        System.out.println();

    }
}
